АЛГОРИТМЫ ПОСТРОЕНИЯ ИНВЕРТИРОВАННОГО ИНДЕКСА ДЛЯ КОЛЛЕКЦИИ ТЕКСТОВЫХ ДАННЫХ

Трифонов Александр Александрович, аспирант, Пензенский государственный университет (Россия, г. Пенза, ул. Красная, 40), alexander.a.trifonov@gmail.com 

004.046 

Актуальность и цель. С геометрическим ростом объемов информации в XXI в. все труднее находить и отбирать полезные и качественные данные. Налицо эффект так называемого «ухудшающего отбора» и большого количества «шума». Особенно эти явления заметны в глобальной компьютерной сети Интернет. При создании информационно-поисковых систем размеры обрабатываемых текстовых коллекций зачастую очень велики, что приводит к необходимости усовершенствования методов и средств построения поисковых систем. Для выделения качественной текстовой информации используются методы и средства поиска и анализа текстовой информации. Для того чтобы избежать последовательного просмотра текстов при выполнении каждого запроса, заранее составляется инвертированный индекс документов, который ставит в соответствие терминам те документы из коллекции, в которых они встречаются. Целью данной работы является подробный анализ существующих алгоритмов построения инвертированного индекса для текстовой коллекции, выделение их достоинств и недостатков. Кроме этого, необходимо сравнить временную сложность анализируемых алгоритмов, что позволит сделать выводы об обоснованности применения каждого из них в том или ином случае.
Материалы и методы. При построении систем информационного поиска многие решения зависят от характеристик компьютерного обеспечения, на котором будет развернута система, поэтому способы построения индекса могут быть разделены на две категории: построение, основанное на памяти, и построение, основанное на диске. Данные проведенных исследований показывают, что производительность алгоритмов построения индекса очень зависит от количества оперативной памяти, доступной процессу индексации. Учитывая специфику алгоритмов индексирования, сравнивать их сложность имеет смысл, когда объем коллекции больше или меньше объема M оперативной памяти ПК, на котором выполняется индексирование.
Результаты. Исследована временная сложность анализируемых алгоритмов построения инвертированного индекса для текстовой коллекции в зависимости от различных параметров. Инвертированный индекс обычно является слишком большим, чтобы быть загруженным полностью в
оперативную память. Если объем оперативной памяти, доступный процессу индексации, является слишком маленьким, чтобы позволить индексу быть созданным полностью в оперативной памяти, то описанный способ построения индекса в памяти может быть расширен до основанного на слиянии метода, в котором текстовый набор динамически делится на поднаборы, исходя из доступного количества оперативной памяти. Проведено сравнение временной сложности анализируемых алгоритмов в зависимости от объема оперативной памяти ПК, на котором выполняется индексирование, что позволяет сделать выводы об обоснованности применения каждого из них в том или ином случае.
Выводы. Построение индекса, основанное на сортировке, стоит применять, когда объем текстовой коллекции не превышает несколько гигабайт. При увеличении объема коллекции более эффективным становится построение индекса, основанное на слиянии. 

Ключевые слова

информационный поиск, коллекция документов, инвертированный индекс, построение индекса. 

 Скачать статью в формате PDF

1. Маннинг, К. Введение в информационный поиск : пер. с англ. / К. Маннинг, П. Рагхаван, Х. Шютце. – М. : Вильямс, 2011. – 528 с.
2. Büttcher, S. Cormack. Information Retrieval: Implementing and Evaluating Search Engines / Stefan Büttcher, Charles L. A. Clarke, and Gordon V. – MIT Press, 2010. – 606 c.
3. Ландэ, Д. В. Интернетика. Навигация в сложных сетях. Модели и алгоритмы / Д. В. Ландэ, А. А. Снарский, И. В. Безсуднов. – М. : Либроком, 2009. – 264 с.
4. Леонтьева, Н. Н. Автоматическое понимание текстов: системы, модели, ресурсы : учеб. пособие для студ. лингв. фак. вузов / Н. Н. Леонтьева. – М. : Академия, 2006. – 304 с.